public class SortAlgorithm {
    public static void main(String[] args) {
        // 1 测试
        int[] testArray = new int[]{9, 2, 1, 6, 16, 4, 5, 8, 7, 10, 23, 21, 80};
        SortAlgorithm.quickSort(testArray);
        for(int i = 0; i < testArray.length; i++) {
            System.out.print(testArray[i] + " ");
        }
    }

    public static void quickSort(int[] array) {
        /**
         * 快速排序接口层
         * */

        // 1 实际递归
        quick(array, 0, array.length-1);
    }

    private static void quick(int[] array, int left, int right) {
        /**
         * 快速排序-递归实现
         * */
        // 1 若是左指针 大于等于 右指针，则返回，因为此时已经全部排序成功
        if(left >= right) {
            return;
        }
        // 2 以第一个元素为基准值，找到基准值下标
        int pivot = partition(array, left, right);
        // 3 递归排序左边 和 右边
        SortAlgorithm.quick(array, left, pivot - 1);
        SortAlgorithm.quick(array, pivot + 1, right);
    }

    private static int partition(int[] array, int left, int right) {
        /**
         * 找基准值
         *  原理：先右后左，左边找到比基准值大的数暂停，右边找到比基准值小的数暂停，交换后继续
         * */
        // 1 保存基准值，及其下标
        int target = array[left];
        int originalIndex = left;
        while(left < right) {
            // -右边
            while(left < right && array[right] >= target) {
                right --;
            }
            // -左边
            while(left < right && array[left] <= target) {
                left ++;
            }
            // -代码运行到此处，即说明left 和 right都找到指定值，交换即可
            swap(array, left, right);
        }
        // 2 出循环，说明left 与 right相遇，交换基准值与相遇点
        swap(array, originalIndex, left);
        // 3 返回相遇点，此时相遇点下标坐标全部小于基准值，右边全部大于基准值
        return left;
    }

    private static void swap(int[] array, int left, int right) {
        /**
         * 交换函数
         * */
        int temp = array[left];
        array[left] = array[right];
        array[right] = temp;
    }
}
